package 代码随想录_动态规划.完全背包;

import java.util.Scanner;

/**
 * @author zx
 * @create 2022-05-31 15:06
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
 * 数据范围：1 ≤ n ≤ 20
 * 问跳到台阶有几种方法其实就是问装满背包有几种方法。
 * 组成部分一：确定状态
 *               最后一步：
 *               子问题：
 *               确定dp数组(dp table)以及下标的含义
 *               dp[i]：跳到有i个台阶的楼顶，有dp[i]种方法。
 * 组成部分一：确定状态
 * 最后一步：
 * 子问题：
 * 组成部分二：转移方程
 * 求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
 * 组成部分三：初始条件和边界情况
 * 递归公式是 dp[i] += dp[i - j],dp[0]一定为1,dp[0]是递归中一切数值的基础,如果dp[0]是0的,其他数值都是0了
 * 组成部分四：计算顺序
 * 这是背包里求排列问题，即：1、2 步  和 2、1 步都是上三个台阶，但是这两种方法不一样！
 * 所以需将target放在外循环，将nums放在内循环。
 */
    public class 跳台阶扩展问题_nowcoder {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i = 1;i <= n;i++){//遍历背包(一次可以跳多少台阶)
            for(int j = 0;j <= n;j++){//遍历物品(总共的台阶数)
                if(i - j >= 0){
                    dp[i] += dp[i - j];//背包要能容的下物品
                }
            }
        }
        System.out.println(dp[n]);
    }
}
